package com.star.niuke;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: liminghui
 * @date: 2021/7/26 14:31
 * @version: 1.0
 * @description: 遍历二叉树
 */
public class BinaryTree {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        TreeNode root1 = new TreeNode(3);
        TreeNode root21 = new TreeNode(9);
        TreeNode root22 = new TreeNode(20);
        TreeNode root31 = new TreeNode(15);
        TreeNode root32 = new TreeNode(7);

        root1.left = root21;
        root1.right = root22;

        root22.left = root31;
        root22.right = root32;

        ArrayList<ArrayList<Integer>> arrayLists = binaryTree.levelOrder(root1);
        System.out.println(arrayLists);
    }

    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList();//用于返回最后的结果
        if (root == null) {
            return res;
        }//如果根节点为空就返回结果
        Queue<TreeNode> q = new LinkedList<TreeNode>();//用于存储每一层的节点
        q.add(root);
        while (!q.isEmpty()) {
            int n = q.size();
            ArrayList<Integer> temp = new ArrayList<>();//用于存储当前遍历这一层的节点
            for (int i = 0; i < n; i++) {
                TreeNode node = q.poll();//取出队列的第一个元素
                temp.add(node.val);//将队头元素保存起来
                if (node.left != null) {
                    q.add(node.left);
                }//左孩子如果不为空就进队列
                if (node.right != null) {
                    q.add(node.right);
                }//右孩子如果不为空就进队列
            }
            res.add(temp);//将这一层的节点数里面据保存到res
        }
        return res;

    }


    // Definition for binary tree
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
